This invention relates to the optimization of register allocation in data processing systems during program compile time. More particularly, this invention relates to register allocation optimization using interference graph coloring techniques.
Register allocation using interference graph coloring techniques is known and has been widely adopted for use in assigning real registers to symbolic or virtual registers when a program is being compiled prior to execution. The standard technique is disclosed in U.S. Pat. No. 4,571,678 and U.S. Pat. No. 5,249,295, the disclosures of which are hereby incorporated by reference. In general, the technique proceeds by creating in the data processing system compiler a register interference graph using symbolic or virtual registers, with the symbolic registers as individual nodes in the graph. For those nodes in which the contents are concurrently live, such nodes are connected by an edge. Once the interference graph is constructed, those nodes having a degree less than k, where k is the number of real registers available in the data processing system, are deleted from the graph in some logical fashion. Nodes of degree greater than or equal to k are selected for a spilling operation, in which the contents of the real registers (when the program is executed) will be stored elsewhere for later recall. A new interference graph is thereafter constructed, and each node is examined in the same fashion. This iterative process continues until all nodes have been removed from the interference graph. Thereafter, the nodes are examined in reverse order and assigned individual colors (in actuality real register numbers) and the process is thus completed.
While generally effective in allocating real registers when a program is being compiled, many specific applications provide conditional constraints which result in less than optimal register allocation as a result of the interference graph coloring technique. For example, in some data processing systems employing single precision floating point operations, real registers are bound together as pairs, with a resulting inability of the data processing system to distinguish between individual registers of a pair. If one of the paired registers is allocated to a first node and the other one of the register pair is allocated to a second node with common latency with the first node (i.e., the first and second nodes are linked with an edge), an interlock condition will exist in which the system must wait several machine cycles for the completion of the execution of a given instruction before the next instruction is permitted to proceed. While the delay in execution introduced by a float interlock condition is usually not so great as that induced by a spill operation, the execution time of that portion of the program still suffers, which is undesirable and less than optimal.